A number of different wireless network topologies are known including ad-hoc, sensors, mesh, and ZigBee networks. The ZigBee network is in the form of a tree due to a distributed addressing scheme.
A route in a wireless network includes a source node, a destination node and optional intermediate nodes. Typically, a source node discovers a route by initiating a route discovery procedure before data frames are transmitted to the destination node. Typically, an optimal route is selected based on a least cost that can include a combination of the following factors: number of hops, expected delay, remaining battery life, reliability; and signal strength between the nodes along the route.
When a source node wants to discover a route to a destination node, the source node broadcasts a route request (RREQ) frame. The RREQ frame identifies the source node, the destination node, accumulated cost, and a unique identification (ID) of the RREQ frame. Each node that receives a RREQ frame determines whether the node is the destination node or not. If the node is not the destination node, then the intermediate node updates the cost and rebroadcasts the frame after a predetermined amount delay. The node rebroadcasts the RREQ frame only once unless a frame with a lower cost is received. In this way, the RREQ frame ultimately reaches the destination node, if one exists.
After receiving a RREQ frame, the receiving node also constructs and sends a route reply (RREP) frame to the originating node of the RREQ frame. The RREP frames can eventually reach the source node. The source node examines addresses in the received RREP frames to discover a least cost route.
It is possible for the destination node to receive multiple copies of the RREQ frame via different routes. In this case, the destination replies only to a subsequently received RREQ frame that has a route with a lower cost. This is a problem.
Conventional route discovery methods assume that a node receiving a RREQ frame can respond to the originating node. However, this may not always be true due to transmission asymmetry. There may be several reasons for an asymmetry of transmission among pairs of nodes, e.g., relative geographic locations of nodes, intervening obstructions, available battery power, and antenna configuration.
Consider the example wireless network 100 shown in FIG. 1 for which the invention is intended. That network includes a source node (S) 101, a destination node (D) 102, and intermediate nodes (I) 103. Wireless communications channels link the nodes. The source node broadcasts the RREQ frame 110. Because the source node has sufficient transmission range, the RREQ frame is received by the destination node, as well as some of the intermediate nodes in the network. These intermediate nodes rebroadcast the RREQ frame, and unicast RREP frames.
The transmission range of the destination node is insufficient for the RREP frame 120 to reach the source node. The destination node also receives the RREQ frames rebroadcast by intermediate nodes 115. The transmission range of the destination node is sufficient for the RREP frame 130 to reach the intermediate node. However, the cost of viable routes via the intermediate nodes is higher than the cost of the unviable route directly linking the source node with the destination node. Therefore, the destination node discards the RREQ frames received via the more costly, but viable routes from the intermediate nodes. In other words, route discovery fails in what could otherwise be a fully functional network.
The same problem can exist for intermediate nodes that receive RREQ frames but cannot reach the originating nodes with RREP frames. After a route has been discovered, the same problem can exist for data frames because of dynamically changing network conditions. In other words, transmission asymmetry is a significant problem in wireless communications networks.
It is desired to solve this problem.
In the prior art, it is known how to verify the integrity of a data path and associated routing elements in a wired TCP/IP network, such the Ethernet or the Internet. In wired networks, devices use what is known as an IP ‘ping’. The ping takes it name from submarine sonar technology that is used discover underwater objects. Short burst of acoustic signals are send out and one ‘listens’ for echoes or pings coming back. In an IP network, the ping function broadcasts a short data burst, i.e., a single packet, and listens for a single packet in reply. The broadcast IP ping packet can be communicated indirectly along multiple hops in the network before reaching the destination and returning to the source. Although the ping mechanism has been used in wired IP networks, applicants believe that the ping according to the invention has not been employed in a wireless network as described hereinafter.